#include "myTree.h"
#include<stack>

using namespace std;

TreeNode* Thrt = new TreeNode(NULL, NULL, NULL, Link, Thread);//设置头节点

void TreeNode::printNode()
{
    cout << this->data;
}

//树节点的初始化
TreeNode::TreeNode(char d, TreeNode* ld, TreeNode* rd, NodeTag lt, NodeTag rt) {
    this->data = d;
    this->leftChild = ld;
    this->rightChild = rd;
    this->lTag = lt;
    this->rTag = rt;
}

TreeNode::~TreeNode() {

}

//树初始化

//无参构造
MyTree::MyTree() {
    this->root = NULL;
    this->isThread = false;
}

//构造函数
MyTree::MyTree(const char c[]) {
    int i = 0;
    this->root = createTree(c, &i);
    this->isThread = false;
}

//拷贝函数
MyTree::MyTree(const MyTree& t) {
    this->root = copyTree(t.root);
    this->isThread = t.isThread;
}

//析构函数
MyTree::~MyTree() {
    DeleteTree(this->root);
    this->root = NULL;
}

//前序遍历
void MyTree::preOrderTraverse() {
    TreeNode* tmp = this->root;
    if (this->isThread == false) {
        preOrder(tmp);
    }
}

//中序遍历
void MyTree::inOrderTraverse() {
    TreeNode* tmp = this->root;
    if (this->isThread == false) {
        inOrder(tmp);
    }
    else {
        inOrderTraverse_Thr(Thrt);
    }
}

//后序遍历
void MyTree::postOrderTraverse() {
    TreeNode* tmp = this->root;
    if (this->isThread == false) {
        postOrder(tmp);
    }
}

//叶结点计数
int MyTree::countLeaf() {
    TreeNode* tmp = this->root;
    if (this->isThread == false) {
        return leafNum(tmp);
    }
    return 0;
}

//树的深度
int MyTree::countHeight() {
    TreeNode* tmp = this->root;
    if (this->isThread == false) {
        return treeHeight(tmp);
    }
    return 0;
}

//是否为线索二叉树
bool MyTree::isThreadedTree() {
     return this->isThread;
}

//中序线索二叉树
TreeNode* pre = NULL;//pre是全局变量
bool MyTree::inOrderThreading() {
    this->isThread = true;
    Thrt->rightChild = Thrt;//头节点右指针回指
    if (!this->root) {
        Thrt->leftChild = Thrt;//如果二叉树为空。则左指针也回指
    }
    else {
        Thrt->leftChild =this->root;
        pre = Thrt;
        inThreading(this->root);
        pre->rTag = Thread;
        pre->rightChild = Thrt;
        Thrt->rightChild = pre;
    }
    return this->isThread;
}

//结点定位
TreeNode& MyTree::locateNode(const char& d) {
    TreeNode* tmp = this->root;
    return *locate(tmp, d);
}

//获取线索二叉树的当前节点的前驱结点
TreeNode& MyTree::preNode(const TreeNode& node) {
    TreeNode* p = node.leftChild;
    if (this->isThread == false) {
        this->inOrderThreading();
    }
    if (node.lTag == Thread) {
          return *(node.leftChild);
    }
    else {
        return *(inOrderLastNode(p));
    }
}

//获取线索二叉树的当前节点的后驱结点
TreeNode& MyTree::nextNode(const TreeNode& node) {
    TreeNode* p = node.rightChild;
    if (this->isThread == false) {
        this->inOrderThreading();
    }
    if (node.rTag == Thread) {
        return *(node.rightChild);
    }
    else {
        return *(inOrderFirstNode(p));
    }
}

//add function-----------------------------------------------------------------------------------
//创建树
TreeNode* MyTree::createTree(const char str[], int* i) {
    if (str[*i] == '\0' || str[*i] == '@') {
        return NULL;
    }
    else {
        TreeNode* p = new TreeNode(str[*i], NULL, NULL, Link, Link);
        ++(*i);
        p->leftChild = createTree(str, i);
        ++(*i);
        p->rightChild = createTree(str, i);
        return p;
    }
}

//复制树
TreeNode* MyTree::copyTree(TreeNode* node) {
    if (!node) {
        return NULL;
    }
    TreeNode* newNode = new TreeNode(node->data, NULL, NULL, Link, Link);
    if (node->leftChild) {
        newNode->leftChild = copyTree(node->leftChild);
    }
    else {
        newNode->leftChild = NULL;
    }
    if (node->rightChild) {
        newNode->rightChild = copyTree(node->rightChild);
    }
    else {
        newNode->rightChild = NULL;
    }
    return newNode;
}

//删除树
void MyTree::DeleteTree(TreeNode* node) {
    if (node == NULL) {
        return;
    }
    if (node->lTag == Link) DeleteTree(node->leftChild);
    if (node->rTag == Link)DeleteTree(node->rightChild);
    delete node;
}

//前序遍历函数
void MyTree::preOrder(TreeNode* node) {
    if (node) {
        node->printNode();
        preOrder(node->leftChild);
        preOrder(node->rightChild);
    }
}

//中序遍历函数(非线索二叉树）
void MyTree::inOrder(TreeNode* node) {
    if (node) {
        inOrder(node->leftChild);
        node->printNode();
        inOrder(node->rightChild);
    }
}

//中序遍历函数(线索二叉树）
void MyTree::inOrderTraverse_Thr(TreeNode* node) {
    TreeNode* temp = node->leftChild;
    while (temp != node) {
         while (temp->lTag == Link) {
             temp = temp->leftChild;
         }
        temp->printNode();
        while (temp->rTag == Thread && temp->rightChild != node) {
            temp = temp->rightChild;
            temp->printNode();
        }
        temp = temp->rightChild;

    }
}

//后序遍历函数
void MyTree::postOrder(TreeNode* node) {
    if (node) {
        postOrder(node->leftChild);
        postOrder(node->rightChild);
        node->printNode();
    }
}

//叶节点计数
int MyTree::leafNum(TreeNode* node) {
    if (!node) {
        return 0;
    }
    else if(!node->leftChild&&!node->rightChild){
        return 1;
    }
    else {
        return leafNum(node->leftChild) + leafNum(node->rightChild);
    }
}

//树的深度
int MyTree::treeHeight(TreeNode* node) {
    if (!node) {
        return 0;
    }
    else {
        int m = treeHeight(node->leftChild);
        int n = treeHeight(node->rightChild);
        return (m > n) ? m + 1 : n + 1;
    }
}

//二叉树中序线索化
void MyTree::inThreading(TreeNode* node) {
    if (node != NULL) {
        inThreading(node->leftChild);
        if (node->leftChild == NULL) {
            node->lTag = Thread;
            node->leftChild = pre;
        }
        if (pre->rightChild == NULL) {
            pre->rTag = Thread;
            pre->rightChild = node;
        }
        pre = node;
        inThreading(node->rightChild);
    }
}

//节点定位
TreeNode* MyTree::locate(TreeNode* node, const char& c) {
    if (node->data == c)
    {
        return node;
    }
    if (node->leftChild && node->lTag != Thread)
    {
        TreeNode* p = locate(node->leftChild, c);
        if (p)
        {
            return p;
        }

    }
    if (node->rightChild && node->rTag != Thread)
    {
        TreeNode* p = locate(node->rightChild, c);
        if (p)
        {
            return p;
        }
    }
    return NULL;
}

//获取中序下此节点右子树的最后一个节点
TreeNode* MyTree::inOrderLastNode(TreeNode* node){
    TreeNode* tmp = node;
    while (tmp->rTag == Link)
    {
        tmp = tmp->rightChild;
    }
    return tmp;
}

//获取中序下此节点左子树的第一个节点
TreeNode* MyTree::inOrderFirstNode(TreeNode* node) {
    TreeNode* tmp = node;
    while (tmp->lTag == Link)
    {
        tmp = tmp->leftChild;
    }
    return tmp;
}

//------------------------------------------------------------------------------------

//构造霍夫曼树的节点
HTNode::HTNode() {
    this->weight = 0;
    this->leftChild = -1;
    this->rightChild = -1;
    this->parent = -1;
    this->code = "";
}

//构造函数
HuffmanTree::HuffmanTree(const int& n, const int data[]) {
    this->Num = n;
    const int leafNum = n;
    const int num = 2 * n - 1;
    HTNode* HFN = new HTNode[2*n-1];
    this->htnode = HFN;
    int* p = new int[n];
    for (int i = 0; i < n; i++) {
        p[i] = data[i];
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n - i - 1; j++)
        {
            if (p[j] < p[j + 1])
            {
                int tmp = p[j];
                p[j] = p[j + 1];
                p[j + 1] = tmp;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        HFN[i].weight = p[i];
    }
    for (int i = leafNum; i < num; i++) {
        int min1 = MaxNum;
        int min2 = MaxNum;
        int pos1=0, pos2=1;
        for (int j = 0; j < i; j++) {
            if (HFN[j].parent == -1) {
                if (HFN[j].weight < min1) {
                    pos2 = pos1; min2 = min1;
                    pos1 = j; min1 = HFN[j].weight;
                }
                else if (HFN[j].weight < min2) {
                    pos2 = j; min2 = HFN[j].weight;
                }
            }
        }
        HFN[i].leftChild = pos1;
        HFN[i].rightChild = pos2;
        HFN[i].weight = HFN[pos1].weight + HFN[pos2].weight;
        HFN[pos1].parent = HFN[pos2].parent = i;
    }
    getCode(2 * n - 2, "", HFN);
}

//析构函数
HuffmanTree::~HuffmanTree() {
    delete[] this->htnode;
}


//得到哈夫曼树的编码
void HuffmanTree::getCode(int idx, string c, HTNode* h) {
    h[idx].code = c;
    if (h[idx].leftChild != -1) {
        getCode(h[idx].leftChild, c + "0", h);
    }
    if (h[idx].rightChild != -1) {
        getCode(h[idx].rightChild, c + "1", h);
    }
}
//哈夫曼树的输出
void HuffmanTree::printHuffmanCodes() {
    int n = this->Num;
    for (int j = 0; j < n; j++) {
        cout << this->htnode[j].weight << ":" << this->htnode[j].code << endl;
    }
}
